/**
 * 多重背包的核心代码
 * for(int v=Limit;v>=start;--v){
 *     D[i][v] |= D[i][v - curV];
 * } 
 * 因此可以将Di设为bitset，直接使用
 * D[i] |= D[i] << curV; 
 */

class Solution {

using vi = vector<int>;
using bitset_t = bitset<4001>;
vector<bitset_t> D;
int N;
int Limit;

public:
    vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int k) {
        array<int, 4001> cnt{0};
        for(auto i : nums) cnt[i] += 1;
        Limit = k;
        N = nums.size();
        D.assign(N + 1, {});
        D[0].set(0);

        // 做一个多重包
        for(int i=1;i<=N;++i){
            auto c = cnt[i];
            D[i] = D[i - 1];
            for(int k=1;k<=c;k<<=1){
                int newV = k * i;
                D[i] |= D[i] << newV;
                c -= k;
            }
            if(c > 0){
                int newV = c * i;
                D[i] |= D[i] << newV;             
            }
        }

        vector<bool> ans(N, false);
        // N直接取答案即可
        ans[N - 1] = D[N][Limit];

        // 反向迭代
        int curCnt = cnt[N];
        for(int x=N-1;x>=1;--x){
            curCnt += cnt[x];
            D[x] = D[x - 1];
            int tmpcnt = curCnt;
            // 开始往后更新，只有一步，就是一个多重背包
            for(int k=1;k<=tmpcnt;k<<=1){
                int newV = k * x;
                D[x] |= D[x] << newV;
                tmpcnt -= k;
            }
            if(tmpcnt > 0){
                auto newV = tmpcnt * x;
                D[x] |= D[x] << newV;
            }
            ans[x - 1] = D[x][Limit];
        } 
        return ans;    
    }
};